#include <bits/stdc++.h>
using namespace std;
int t, k, n, m;
const int N = 2005;
int c[N][N], s[N][N];
void prepare() {
  // 归纳基础
  c[1][1] = 1;
  for (int i = 0; i <= 2000; ++i) c[i][0] = 1;
  // 递推组合数
  for (int i = 2; i <= 2000; ++i) {
    for (int j = 1; j <= i; ++j) {
      c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % k;
    }
  }
  for (int i = 2; i <= 2000; ++i) {
    for (int j = 1; j <= i; ++j) {
      // 容斥原理，矩阵求和
      s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
      // 如果是整除，答案增加1
      if (c[i][j] == 0) s[i][j] += 1;
    }
    // 向后更新一步
    s[i][i + 1] = s[i][i];
  }
}
int main() {
  cin >> t >> k;
  prepare();
  while (t--) {
    cin >> n >> m;
    if (m > n) m = n;
    cout << s[n][m] << endl;
  }
  return 0;
}
